from tools_algorithm import *


class Solution:
    def minReverseOperations(
        self, n: int, p: int, banned: List[int], k: int
    ) -> List[int]:

        even = list(range(n + 1))  # n 防 find(a,i) i越界
        odd = list(range(n + 1))

        def find(a, i):
            if a[i] != i:
                a[i] = find(a, a[i])
            return a[i]

        def merge(a, i, j):
            ai, aj = find(a, i), find(a, j)
            a[ai] = aj

        def f(i):
            return find(even, i) if i & 1 == 0 else find(odd, i)

        def delete(i):
            if i & 1 == 0:
                merge(even, i, i + 1)
            else:
                merge(odd, i, i + 1)

        for i in range(n):
            if i & 1 == 0:
                merge(odd, i, i + 1)  # 奇数集合里偶数不要了
            else:
                merge(even, i, i + 1)  # 偶数集合奇数不要了
        delete(p)  # p从集合中删除
        for i in banned:
            delete(i)  # banned从集合删除
        ans = [-1] * n
        ans[p] = 0
        q = deque([p])
        while q:
            i = q.popleft()
            L = max(i - k + 1, k - 1 - i)
            R = min(i + k - 1, (n - k) + (n - 1) - i)
            while (j := f(L)) <= R:
                ans[j] = ans[i] + 1
                q.append(j)
                delete(j)
        return ans


s = Solution()
print(s.minReverseOperations(4, 2, [], 4))

# even = [v if v & 1 == 0 else v + 1 for v in range(5)]
# print(even)
# odd = [v if v & 1 == 1 else v + 1 for v in range(5)]
# print(odd)
